package com.Algorithm;

import java.util.Arrays;

/**
 * 直接插入排序
 *
 * @author yisl
 * @create 2019-06-10 11:23
 */
public class InsertionSort {


    /** 
    * @Description: 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。 
    * @Param:  
    * @return:  
    * @Author: yisl
    * @Date:  
    */
    public static void insertionSort(int[] arr) {
        for (int i=0; i<arr.length; i++){

            //待插入数据
            int insertVal = arr[i];
            //待插入的位置
            int index = i - 1;
            while (index > -1 && insertVal < arr[index]){

                arr[index + 1] = arr[index];
                index --;

            }
            arr[index + 1] = insertVal;
        }
    }

    //在写一遍
    public static void insertSort2(int[] a) {

        for(int i = 1; i < a.length; i++){
            int insertVal = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > insertVal){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = insertVal;
        }

    }

    public static void insertSort3(int[] a){
        for (int i = 0; i < a.length; i++) {
            int insertVal3 = a[i];
            int j=i-1;
            while (j>=0 && a[j]>insertVal3){
                a[j+1] = a[j];
                j--;
            }
            a[j+1]=insertVal3;
        }
    }



    /** 
    * @Description: 主函数
    * @Param: [args] 
    * @return: void 
    * @Author: yisl
    * @Date: 2019-06-10 
    */
    public static void main(String[] args) {
        int[] array = {7, 2, 5, 4, 1, 9};
        InsertionSort.insertSort3(array);
        System.out.println(Arrays.toString(array));
    }

}
